package linkedtable;

import org.junit.Test;

/**
 * @Description 92. 反转链表 II
 * @Author Firenut
 * @Date 2023-02-21 19:48
 */
public class T92_reverseBetween {
    @Test
    public void test() {
        ListNode head = new ListNode(3);
        ListNode tail = new ListNode(5);
        head.next = tail;
        tail.next = null;

        reverseBetween(head, 1, 2);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dump = new ListNode(); //使用dump结点方便处理
        dump.next=head;
        ListNode pre=dump;
        // 指针移动到left的前一个结点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 指针移动到right结点
        ListNode tail = pre;
        for (int i = 0; i < right - left + 1; i++) {
            tail = tail.next;
        }
        // 记录反转链表的下一个结点
        ListNode next = tail.next;

        // 记录left位置的结点
        ListNode begin = pre.next;

        // 断开链表
        pre.next = null;
        tail.next = null;

        // 反转链表，得到反转链表的头节点
        ListNode node = reverse(begin);

        pre.next = node;
        begin.next = next;

        // 不能直接返回head结点，因为它也可能被反转了
        // 比如这个测试案例: [3,5] left=1 right=2
        return dump.next;
//        return head;
    }

    // 反转链表
    ListNode reverse(ListNode head) {
        ListNode cur, pre, next;
        cur = head;
        pre = null;
        next = cur.next;
        while (next != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = next.next;
        }
        cur.next = pre;
        return cur;
    }
}